#include "stack.h"

// Node, *Stack;

Node * NewNode(int x, int y)
{
    Node * node = (Node *) malloc(sizeof(Node));
    node->x = x;
    node->y = y;
    node->dir = 1;
    node->next = NULL;
    return node;
}

Stack InitStack(Stack head)
{
    head = (Stack)malloc(sizeof(Node));
    head->next = NULL;
    head->x = -1;
    head->y = -1;
    head->dir = -1;
    return head;
}

Node * PopStack(Stack stack, Node * target)
{
    target = stack->next;
    stack->next = target->next;
    return target;
}

Stack PushStack(Stack stack, Node * srNode)
{
    srNode->next = stack->next;
    stack->next = srNode;
    return stack;
}

int IsNew(int x, int y, int maze[][12])
{
    if (maze[x][y] == 1)
    {
        return 1;
    }
    else
    {
        return 0;
    } 
}

int IsSafe(int x, int y, int maze[][12])
{
    if (maze[x][y] == 0)
    {
        return 0;
    }
    return 1;
    
}

int SetFlags(int x, int y, int maze[][12])
{
    maze[x][y] = 1;
    return 0;
}

Node * NextPose(Node * cur)
{
    if (cur->dir <=3 && cur->dir >=1)
    {
        if(cur->y > 0)
            cur->y -= 1;
    }
    if (cur->dir <= 7 && cur->dir >= 5)
    {
        if(cur->y < 11)
            cur->y += 1;
    }
    if (cur->dir == 1 || cur->dir == 7 || cur->dir == 8)
    {
        if(cur->x > 0)
            cur->x -= 1;
    }
    if (cur->dir >= 3 && cur->dir <= 5)
    {
        if (cur->x < 11)
            cur->x += 1;
    }

    return cur;
}

int IsEmpty(Stack stack)
{
    if (stack->next == NULL)
    {
        return 0;
    }
    return 1;
}

Stack Resolve(int maze[][12], int x, int y)
{
    if(2 != maze[x][y])
    {
        printf("entrance args error !\n");
        return NULL;
    }
    Stack path;
    InitStack(path);
    Node * curNode = NewNode(x, y);
    PushStack(path, curNode);
    NextPose(curNode);

    while(1)
    {
        if(!IsSafe(curNode->x, curNode->y, maze)&&
            !IsNew(curNode->x, curNode->y, maze))
        {
            SetFlags(curNode->x, curNode->y, maze);
            PushStack(path, curNode);
            if (maze[curNode->x][curNode->y] == -2)
            {
                return path;
            }
            else
            {
                NextPose(curNode);
            }
        }
        else
        {
            if (IsEmpty(path))
            {
                PopStack(path, curNode);
                while(curNode->dir < 9)
                {
                    curNode->dir++;
                    NextPose(curNode);
                    SetFlags(curNode->x, curNode->y, maze);
                    if (!IsSafe(curNode->x, curNode->y, maze) &&
                        !IsNew(curNode->x, curNode->y, maze))
                    {
                        break;
                    }
                }
            }
            else 
            {
                return path;
            }
        }        
    }
}

void PrintPath(Stack path)
{
    if(!IsEmpty(path))
    {
        printf("path empty\n");
    }
    else
    {
        Node * p = path->next;
        while(NULL != p)
        {
            printf("(%d, %d)\n", p->x, p->y);
        }
    }
}

